/*
 * @lc app=leetcode.cn id=1706 lang=cpp
 *
 * [1706] 球会落何处
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
    vector<int> findBall(vector<vector<int>> &grid) {
        int n = grid[0].size();
        vector<int> ans(n, -1);
        for (int j = 0; j < n; ++j) {
            int col = j; // 球的初始列
            for (auto &row : grid) {
                int dir = row[col];
                col += dir; // 移动球
                if (col < 0 || col == n || row[col] != dir) { // 到达侧边或 V 形
                    col = -1;
                    break;
                }
            }
            if (col >= 0) {  // 成功到达底部
                ans[j] = col;
            }
        }
        return ans;
    }
};
// @lc code=end

//递归
    // vector<int> findBall(vector<vector<int>>& grid) {
    //     int n = grid[0].size();
    //     vector<int> ret;
    //     for(int i=0;i<n;i++) {
    //         ret.push_back(dfs(i,0,grid));
    //     }
    //     // for(auto x: ret) {
    //     //     cout<<x<<' ';
    //     // }
    //     return ret;
    // }
    // /**
    //  * @brief in:入口，k：层数
    //  * 
    //  */
    // int dfs(int in,int k,vector<vector<int>>& grid) {
    //     //列举碰壁的各种情况
    //     if((in == 0 && grid[k][in] == -1)||(in == grid[0].size()-1 && grid[k][in] == 1)) {
    //         return -1;
    //     }
    //     if((grid[k][in] == 1 && grid[k][in+1] == -1)||(grid[k][in] == -1 && grid[k][in-1] == 1)) {
    //         return -1;
    //     }
    //     if(k == grid.size()-1) {
    //         return in+grid[k][in];
    //     }
        
    //     return dfs(in+grid[k][in],k+1,grid);
    // }

